/**
 * 统计[1, N]的1的数量 
 * 直接返回cnt
 */
using llt = long long;

vector<int> G;
// Di, i表示当前位, j表示到目前位置的1的数量
llt D[10][10];
int Target;
llt dfs(int pos, int cnt, bool lead, bool limit){
    if(-1 == pos) {
        return cnt; // 这里不返回1，返回cnt
    }
    if(not lead and not limit and -1 != D[pos][cnt]) {
        return D[pos][cnt];
    }

    int last = limit ? G[pos] : 9;
    llt ans = 0;
    
    for(int i=0;i<=last;++i){ 
        ans += dfs(pos - 1, cnt + (1==i?1:0), lead&&0==i, limit&&last==i);
    }
    if(not lead and not limit){
        D[pos][cnt] = ans;
    }    
    return ans;
}

llt digitDP(llt n){
    static int const JINZHI = 10;
    G.clear();
    while(n){
        G.emplace_back(n % JINZHI);
        n /= JINZHI;
    }
    llt ans = 0;
    ans = dfs(G.size() - 1, 0, true, true);
    return ans;
}

class Solution {
public:
    int countDigitOne(int n) {
        memset(D, -1, sizeof(D));
        return digitDP(n);
    }
};